翻訳と辞書 Words near each other ・ Random measure ・ Random minimal spanning tree ・ Random modulation ・ Random neural network ・ Random number ・ Random number book ・ Random number generation ・ Random number generator attack ・ Random number table ・ Random optimization ・ Random oracle ・ Random orbital sander ・ Random Passage ・ Random password generator ・ Random permutation ・ Random permutation statistics ・ Random phase approximation ・ Random phase multiple access ・ Random plot generator ・ Random positioning machine ・ Random projection ・ Random Quest ・ Random Recipe ・ Random regular graph ・ Random Roads Collection ・ Random search ・ Random seed ・ Random self-reducibility ・ Random sequence ・ Random Shoes Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Random permutation statistics ： ウィキペディア英語版 Random permutation statistics The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. Suppose, for example, that we are using quickselect (a cousin of quicksort) to select a random element of a random permutation. Quickselect will perform a partial sort on the array, as it partitions the array according to the pivot. Hence a permutation will be less disordered after quickselect has been performed. The amount of disorder that remains may be analysed with generating functions. These generating functions depend in a fundamental way on the generating functions of random permutation statistics. Hence it is of vital importance to compute these generating functions. The article on random permutations contains an introduction to random permutations. == The fundamental relation == Permutations are sets of labelled cycles. Using the labelled case of the Flajolet–Sedgewick fundamental theorem and writing $\backslash scriptstyle\backslash mathcal$ for the set of permutations and $\backslash scriptstyle\backslash mathcal$ for the singleton set, we have :$\backslash mathfrak(\backslash mathfrak(\backslash mathcal))\; =\; \backslash mathcal.$ Translating into exponential generating functions (EGFs), we have :$\backslash exp\; \backslash log\; \backslash frac\; =\; \backslash frac$ where we have used the fact that the EGF of the set of permutations (there are ''n''! permutations of ''n'' elements) is :$\backslash sum\_\; \backslash frac\; z^n\; =\; \backslash frac.$ This one equation will allow us to derive a surprising number of permutation statistics. Firstly, by dropping terms from $\backslash scriptstyle\backslash mathfrak$, i.e. exp, we may constrain the number of cycles that a permutation contains, e.g. by restricting the EGF to $\backslash scriptstyle\backslash mathfrak\_2$ we obtain permutations containing two cycles. Secondly, note that the EGF of labelled cycles, i.e. of $\backslash scriptstyle\backslash mathfrak(\backslash mathcal)$, is :$\backslash log\; \backslash frac\; =\; \backslash sum\_\; \backslash frac$ because there are ''k''! / ''k'' labelled cycles. This means that by dropping terms from this generating function, we may constrain the size of the cycles that occur in a permutation and obtain an EGF of the permutations containing only cycles of a given size. Now instead of removing and selecting cycles, let's put different weights on different size cycles. If $\backslash scriptstyle\; b(k):\; \backslash mathbb\; \backslash rightarrow\; \backslash mathbb$ is a weight function that depends only on the size ''k'' of the cycle and for brevity we write :$b(\backslash sigma)\; =\; \backslash sum\_\; b(c)$ the value of ''b'' for a permutation $\backslash sigma$ to be the sum of its values on the cycles, then we may mark cycles of length ''k'' with ''u''''b''(''k'') and obtain a bivariate generating function ''g''(''z'', ''u'') that describes the parameter, i.e. :$g(z,\; u)\; =$ 1 + \sum_ \left( \sum_ u^ \right) \frac = \exp \sum_ u^ \frac This is a mixed generating function which is exponential in the permutation size and ordinary in the secondary parameter ''u.'' Differentiating and evaluating at ''u'' = 1, we have :$\backslash frac\; g(z,\; u)\; \backslash Bigg|\_\; =$ \frac \sum_ b(k) \frac = \sum_ \left( \sum_ b(\sigma) \right) \frac i.e. the EGF of the sum of ''b'' over all permutations, or alternatively, the OGF, or more precisely, PGF (probability generating function) of the expectation of ''b''. This article uses the coefficient extraction operator (), documented on the page for formal power series. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Random permutation statistics」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.